﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GreatestSubsequentialSum
{
    public static class ArrayExtension
    {
        public static void LargestSumContiguousSubarray(this int[] input)
        {
            int sum = 0, maxsum = 0, beginmax = 0, endmax = 0;

            for (int i = 0; i < input.Length; i++)
            {
                sum = 0;
                for (int j = i; j < input.Length; j++)
                {
                    sum += input[j];
                    if (sum > maxsum)
                    {
                        maxsum = sum;
                        beginmax = i;
                        endmax = j;
                    }
                }
            }

            Console.WriteLine("Sum: {0}", maxsum);
            Console.WriteLine("Begin: {0} - End {1}", beginmax, endmax);
            Console.Write("Values: ");
            for (int i = beginmax; i <= endmax; i++)
                Console.Write(" {0} ", input[i]);

        }

        public static int LargestSumContiguousSubarrayOptimized(this int[] input)
        {
            int max_sum = 0;
            int current_sum = 0;

            int begin = 0;
            int end = 0;

            for (int i = 0; i < input.Length; i++)
            {
                current_sum += input[i];

                if (current_sum < 0)
                {
                    current_sum = 0;
                    begin = i + 1;
                }

                if (max_sum < current_sum)
                {
                    max_sum = current_sum;
                    end = i;
                }
            }

            Console.WriteLine("Max Sum: {0} found between index {1} - {2}", max_sum, begin, end);

            return max_sum;
        }
    }
}
